The rapid growth in recent years of wired and wireless communications has strained traditional forms of modulated transmission. For traditional single-carrier modulation systems to scale with the need for high data rate communications, increasingly costly and complex equalizers have been employed. To solve the problem of increasingly expensive equalizers, multi-carrier (MC) communication systems have been developed. MC communication systems work by dividing a transmission bandwidth into a plurality of smaller sub-channels, with a fixed total number of transmission bits, where the bandwidth of each channel is chosen narrow enough in frequency such that the sub-channels exhibit nearly ideal frequency response characteristics. An essential problem in MC communication systems is optimally allocating a fixed number of transmission bits over several frequency ranges or sub-channels so that the most efficient signal transmission is achieved.
A parallel problem exists in the area of digital multimedia compression, where there is an increasing need for large multimedia files to be compressed for convenience, storage, and transmission. Multimedia files often contain digital representations of signals such as sound and video. All such signals can be expressed in terms of signal frequencies such as color in video. In analogy to MC communication systems, one class of compression schemes, known as sub-band coding, decomposes the signal to be compressed into several frequency ranges or bands, known as sub-bands, and compress each sub-band separately according to its relative importance in the overall signal representation. A compression scheme such as JPEG or MPEG must then choose how to best allocate a fixed number of bits over various sub-bands so that the resulting image is the best possible reproduction of the original. Choosing exactly how to allocate bits among various sub-frequencies is thus an essential component of sub-band coding.
As discussed above and as known in the art, both MC communications and sub-band coding require a solution to the analogous problem of intelligently distributing a fixed number of bits among a set of frequency ranges in an input signal. Thus, the principles, problems, and analysis of bit loading in MC communications are equally applicable to sub-band coding, and vice versa. To provide the proper context for understanding bit loading in the art, forms of MC communications and sub-band coding are discussed below.
In MC communication systems as known in the art, we have k=w/Δf sub-channels, allowing information symbols to be transmitted simultaneously in k sub-channels. This type of data transmission system is known as frequency-division multiplexing (FDM). A carrier is associated with each sub-channel, such that:xk(t)=sin 2πfkt for k=0,1,2, . . . k−1.
For each k sub-channel, fk represents the mid-frequency. The symbol rate can be set to 1/T on each of the sub-channels to equal the separation Δf of the adjacent sub-channels, making the sub-channels orthogonal over the symbol interval T, such that:fk−fj=n/T for n=1,2,3, . . . .
Therefore, the phases between the channels are independent, creating what is known in the art as orthogonal frequency division multiplexing (OFDM). In an OFDM system, the modulator can be implemented by a parallel bank of filters executing the Inverse Discrete Fourier Transform (IDFT) transformation of N data streams, where each data stream corresponds to one sub-channel. Likewise, the demodulator can be implemented by a parallel bank of filters executing the Discrete Fourier Transform (DFT) transformation. Modulation and demodulation can also be carried out in software operative on a microprocessor such as an Intel compatible x-86 microprocessor.
FIG. 1 depicts the first step in the serial to parallel signal conversion process, where a serial data stream s(n) is input and divided into N parallel data streams zi(n).
FIG. 2 depicts an equivalent model of a Discrete Multi-Tone (DMT) communication system, known in the art as a baseband model. DMT is a general framework for MC systems of which OFDM is a special case. In OFDM, an N-point block Inverse Discrete Fourier Transform (IDFT) transformation of these streams of data is followed by a parallel to serial conversion, then transmission after adding cyclic prefix redundancy data. At channel output the system performs in reverse-step the operations of redundancy removal, serial to parallel conversion, and the application of a block Discrete Fourier Transform (DFT) transformation to arrive at a representation of the original input data. More general DMT systems involve more general transforms replacing the DFT and IDFT transform blocks, and more schemes of redundancy insertion and removal may be used.
While an MC communication system, either in its specific form of OFDM or in a more general DMT framework, can obviate the need for an expensive equalizer, it creates bit allocation problems such as determining the optimal bit distribution given variable transmission conditions, power allocation among sub-channels, total transmission power, and the Peak-to-Average (PAR) power ratio among sub-channels.
An example sub-band coder is illustrated FIG. 3. In FIG. 3, each Qk is a bk bit quantizer. The arrangement preceding these quantizers is known in the art as the analysis block, which decomposes the signal to be compressed, Zk, into the sub-band signals at the input of the quantizers. The block following the quantizers is known as the synthesis block, which reconstructs the signal Zk. The goal in sub-band coding is to assign bits bk to minimize the overall distortion in the reconstructed signal. The overall error in reconstructing Zk is as in (1, 3), with:φk(bk)=σ2k2−2bk.
Here σ2k is the variance of the k-th sub-band signal (vk), determined by the statistics of Z and the filters Hk. This is captured by the minimization in (1, 2) under (3).
The problem of bit allocation among a plurality of frequency ranges is known as bit loading in the art. Specifically, for an N sub-channel system, where bk is the number of bits assigned to each symbol in the cognizant sub-channel, the problems of minimizing the transmission power in MC communications or minimizing the distortion in sub-band coding are special cases of the general problem of finding bk to:                Minimize:        
                              P          ⁡                      (                                          b                1                            ,              …              ⁢                                                          ,                              b                N                                      )                          =                              ∑                          k              =              1                        N                    ⁢                                          ⁢                                    ϕ              k                        ⁡                          (                              b                k                            )                                                          (        1        )                            Subject to:        
                                                        ∑                              k                =                1                            N                        ⁢                                                  ⁢                          b              k                                =          B                ,                                  ⁢                              b            k                    ∈                                    {                              0                ,                1                ,                …                ⁢                                                                  ,                B                            }                        .                                              (        2        )            where φk is a convex function, and B is a positive integer representing the total number of bits to be distributed among N frequency ranges, such as N sub-channels or sub-bands. In sub-band coding:φk(bk)=αk2−bk, αk>0;  (3)where αk is determined by the signal variance in the k-th sub-band, P(b1, . . . , bN) is the average distortion variance, and bk is the bits assigned to the k-th sub-band. Further, αk increases with increasing signal variance. In MC systems:φk(bk)=αk2bk, αk>0;  (4)where αk reflects target performance, channel and interference conditions experienced in the k-th sub-channel, the modulation scheme used, and where φk(bk) is the transmission power in the k-th sub-channel, and P(b1, . . . , bN) is the total transmitted power. Higher values of αk reflect more adverse sub-channel conditions and/or stringent performance goals.
It is recognized that for general convex functions φk, the above constrained minimization grows in complexity with the size of B. Since B can be large, it is important to formulate algorithms for which the complexity bound is independent of B. Accordingly, what is needed is an algorithm whose complexity is independent of B, when φ is as in (5), below. Observe this captures both (3) (η=−2; a=2) and (4) (η=1; a=2):φk(bk)=αkaηbk, αk>0.  (5)
As an example, in a MC communication system, ek denotes the signal power in the k-th sub-channel, and is given by:ek=αk2bk−αk.
Here, αk represents the target channel performance given the channel and interference conditions experienced in the k-th sub-channel:
      α    k    =      2    ⁢                                        Γ            k                    ⁢                      σ            k            2                                    G          2          k                    .      
Depending on the modulation scheme employed, and the precise DMT scheme used (which may be different from OFDM), ek may take a slightly different form, but the optimization problem in (1, 2), under (5), still captures the power minimization problem in all MC schemes.
Several bit loading algorithms exist in the art which attempt to efficiently allocate B bits among N sub-channels. However, these methods provide solutions which grow with the size of B or restrict the size of B, providing algorithm run times which are too long to be practical when the number of bits B is large, or unrealistically restrict the size of B.
J. Campello, “Practical bit loading for DMT”, IEEE International Conference on Communications, pp 801-805, 1999, provides a prior art algorithm for allocating B bits among N sub-channels. Campello's algorithm restricts the maximum number of bits to be assigned to any sub-channel to some B* and thereby provides a bit allocation algorithm with a run time of O(N). The assumption of small B* is problematic in sub-band coding, and even in MC communications settings when certain sub-channels experience deep fades. In such a case, efficiency may demand that a large number bits be assigned to sub-channels with more favorable conditions. Another contributor to the complexity of Campello's algorithm is the dynamic range of αi, which comes into play in the presence of deep fades.
B. S. Krongold, K. Ramchandran and D. L. Jones, “An efficient algorithm for optimal margin maximization in multicarrier communication systems”, IEEE Global Telecommunications Conference, pp 899-903, 1999, provides a prior art bit loading algorithm whose complexity grows with O(N log N), and linearly with B. Thus, as the total number of bits B becomes large, the Krongold, Ramchandran bit loading algorithm becomes impractical, especially when bits must be allocated to sub-channels in real-time.
Thus, prior art systems provide bit loading algorithms that either grow with the size of B, making the algorithm run time too large to be computationally efficacious, or only provide solutions when the number of total bits is restricted to an unrealistically small number B*. Therefore, what is needed is a solution to the bit loading problem illustrated by (1, 2), and (5) whose complexity has an upper bound that is determined only by N, and where the role of B is only to induce cyclic fluctuations in the precise number of computations, and neither B nor the dynamic range of αk, affects the upper bound of the runtime.